class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}

private boolean isValidBST(TreeNode node, Integer lower, Integer upper) {
if (node == null) {
return true;
}
int val = node.val;
if (lower != null && val <= lower) {
return false;
}
if (upper != null && val >= upper) {
return false;
}
if (!isValidBST(node.right, val, upper)) {
return false;
}
if (!isValidBST(node.left, lower, val)) {
return false;
}
return true;
}
}


class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
TreeNode minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
return root;
}

private TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
}

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
}

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
}